class Solution {
    public int largestRectangleArea(int[] heights) {
        int len = heights.length;
        int[] h = new int[len+2];
        // 在index=0,index=len添加哨兵
        System.arraycopy(heights,0,h,1,len);

        Deque<Integer> st = new LinkedList<>();
        st.addLast(0);
        int ans = 0;
        for (int i = 1; i <= len+1; i++) {
            while (st.size() > 0 && h[i] < h[st.getLast()]) {
                int rIndex = st.removeLast();
                int lIndex = st.getLast();
                ans = Math.max(ans, h[rIndex] * (i - lIndex-1));
//                    System.out.println(rIndex+": "+(h[rIndex] * (i - lIndex-1)));
            }
            // 表示矩形可以继续向右扩展
            st.addLast(i);
        }

        return ans;
    }
}